package www.study.com;

import java.util.*;

//电话号码的字母组合 https://leetcode.cn/problems/letter-combinations-of-a-phone-number/
public class code16 {
    public static void main(String[] args) {

    }

    class Solution {
        public List<String> letterCombinations(String digits) {
            List<String> res = new ArrayList<String>();
            if(digits == null || digits.length() == 0) return res;
            Map<Integer, List<String>> map = new HashMap<Integer, List<String>>();
            initMap(map);
            StringBuilder sb = new StringBuilder();
            func(map, digits.toCharArray(), 0, sb, res);
            return res;
        }
        public void func(Map<Integer, List<String>> map, char[] chs, int index, StringBuilder sb, List<String> res){
            if(index >= chs.length){
                res.add(sb.toString());
                return;
            }
            List<String> numToChar = map.get(chs[index] - '0');
            for(int i = 0 ; i < numToChar.size() ; i++){
                sb.append(numToChar.get(i));
                func(map, chs, index + 1, sb, res);
                sb.deleteCharAt(sb.length() - 1);
            }
        }
        public void initMap(Map<Integer, List<String>> map){
            map.put(2, new ArrayList<String>(Arrays.asList("a","b","c")));
            map.put(3, new ArrayList<String>(Arrays.asList("d","e","f")));
            map.put(4, new ArrayList<String>(Arrays.asList("g","h","i")));
            map.put(5, new ArrayList<String>(Arrays.asList("j","k","l")));
            map.put(6, new ArrayList<String>(Arrays.asList("m","n","o")));
            map.put(7, new ArrayList<String>(Arrays.asList("p","q","r","s")));
            map.put(8, new ArrayList<String>(Arrays.asList("t","u","v")));
            map.put(9, new ArrayList<String>(Arrays.asList("w","x","y","z")));
        }
    }
}
